
#ifndef _DEQUE_H_
#define _DEQUE_H_





/// <summary>
/// 队列的结构体
/// </summary>
typedef struct _deque_
{
	void* data_buffer;     //数据数组缓存
	int Capacity;     //队列容量。实际容量是Capacity-1

	//数据结构在运行的时候，只有这两个指针会活动。
	//head==tail为空。  head==（tail+1）% Capacity 为满。
	int head;         //头部的地址索引。head取。    （把data_buffer看成是元素类型长度是data_typesize的数组。）  
	int tail;         //尾部的地址索引。tail不取。

}Deque;


/// <summary>
/// 初始化队列
/// </summary>
/// <param name="deque">队列结构体</param>
/// <param name="buf">队列的缓存数组，内存大小是sizeof_data*data_count字节</param>
/// <param name="data_count">队列元素数组的长度</param>
#define deque_init(deque, buf, data_count) \
{ \
	deque.data_buffer = (void*)buf; \
	deque.Capacity = data_count; \
	deque.head = 0; \
	deque.tail = 0; \
}

/// <summary>
/// 清空队列
/// </summary>
/// <param name="deque">队列结构体</param>
#define deque_clear(deque) \
{ \
	deque.head = 0; \
	deque.tail = 0; \
}

/// <summary>
/// 计算队列元素的个数
/// </summary>
/// <param name="deque">队列结构体</param>
/// <returns>队列的元素个数</returns>
#define deque_count(deque) ((deque.Capacity + deque.tail - deque.head) % deque.Capacity)


/// <summary>
/// 队列是否是空的
/// </summary>
/// <param name="deque">队列结构体</param>
/// <returns>空返回true，非空返回false</returns>
#define deque_is_empty(deque)   (deque.head == deque.tail)


/// <summary>
/// 队列是否是满的
/// </summary>
/// <param name="deque">队列结构体</param>
/// <returns>满返回true，不满返回false</returns>
#define deque_is_full(deque)    (deque.head == ((deque.tail + 1) % deque.Capacity))


/// <summary>
/// 从队列头部弹出数据
/// </summary>
/// <param name="deque">队列结构体</param>
#define deque_pop_front( deque)	if (deque_is_empty(deque) == false) \
{ \
	deque.head = (deque.head + 1) % deque.Capacity; \
}

/// <summary>
/// 从队列尾部弹出数据
/// </summary>
/// <param name="deque">队列结构体</param>
/// <returns>弹出的数据。如果队列空了，返回0</returns>
#define deque_pop_back( deque)	if (deque_is_empty(deque) == false) \
{ \
	deque.tail = (deque.tail + deque.Capacity - 1) % deque.Capacity; \
}

/// <summary>
/// 从头部弹出n个元素。
/// </summary>
/// <param name="deque">队列结构体</param>
/// <param name="n">弹出元素的个数。如果没有那么多元素，就清空队列。</param>
#define deque_pop_front_n( deque, n) if (n > 0) { \
	if (n < deque_count(deque)) { \
		deque.head = (deque.head + n) % deque.Capacity; \
	} \
	else \
	{ \
		deque_clear(deque);  \
	} \
}

/// <summary>
/// 从尾部弹出n个元素。
/// </summary>
/// <param name="deque">队列结构体</param>
/// <param name="n">弹出元素的个数。如果没有那么多元素，就清空队列。</param>
#define deque_pop_back_n( deque,  n) { \
	if (n > 0) { \
		if (n < deque_count(deque)) { \
			deque.tail = (deque.tail - n + deque.Capacity) % deque.Capacity; \
		} \
		else \
		{ \
			deque_clear(deque); \
		} \
	} \
}




/// <summary>
/// 寻找队列开头的第n个元素
/// </summary>
/// <param name="deque">队列结构体</param>
/// <param name="n">队列索引号</param>
/// <param name="data_type">队列元素类型</param>
/// <returns>返回队列开头的索引号对应的元素，如果索引号超出范围，会循环</returns>
#define deque_index_head(deque,n,data_type)    ( ((data_type*)deque.data_buffer)[(deque.head + n) % deque.Capacity] )

/// <summary>
/// 寻找队列末端的第n个元素，这里n从1起步。
/// </summary>
/// <param name="deque">队列结构体</param>
/// <param name="n">队列索引号</param>
/// <param name="data_type">队列元素类型</param>
/// <returns>返回队列开末端的索引号对应的元素，如果索引号超出范围，会循环</returns>
#define deque_index_tail(deque,n,data_type)    ( ((data_type*)deque.data_buffer)[(deque.tail - n + deque.Capacity) % deque.Capacity] )


/// <summary>
/// 寻找队列头节点
/// </summary>
/// <param name="deque">队列结构体</param>
/// <param name="data_type">队列元素类型</param>
#define deque_head(deque,data_type)  ( ((data_type*)deque.data_buffer)[deque.head] ) 


/// <summary>
/// 寻找队列尾节点
/// </summary>
/// <param name="deque">队列结构体</param>
/// <param name="data_type">队列元素类型</param>
#define deque_tail(deque,data_type)  ( ((data_type*)deque.data_buffer)[(deque.tail + deque.Capacity - 1) % deque.Capacity] ) 


/// <summary>
/// 队列头部添加数据，如果不满，才能添加。
/// </summary>
/// <param name="deque">队列结构体</param>
/// <param name="data">添加的元素数据</param>
/// <param name="data_type">队列元素类型</param>
#define deque_push_front(deque,data, data_type)  if(!deque_is_full(deque)) \
{  \
deque.head = (deque.head - 1 + deque.Capacity) % deque.Capacity; \
((data_type*)deque.data_buffer)[deque.head] = data; \
} 


/// <summary>
/// 队列尾部添加数据，如果不满，才能添加。
/// </summary>
/// <param name="deque">队列结构体</param>
/// <param name="data">待添加的数据。如果队列满了，不执行操作</param>
/// <param name="data_type">队列元素类型</param>
#define deque_push_back(deque,data, data_type)  if(!deque_is_full(deque)) \
{  \
((data_type*)deque.data_buffer)[deque.tail] = data; \
deque.tail = (deque.tail + 1) % deque.Capacity; \
}

/// <summary>
/// 队列头部添加数据，如果队列满了，弹出尾部元素再插入
/// </summary>
/// <param name="deque">队列结构体</param>
/// <param name="data">添加的元素数据</param>
/// <param name="data_type">队列元素类型</param>
#define deque_strong_push_front(deque,data, data_type)  {  \
	if (deque_is_full(deque)) { \
		deque.tail = (deque.tail - 1 + deque.Capacity) % deque.Capacity; \
		deque.head = (deque.head - 1 + deque.Capacity) % deque.Capacity; \
		((data_type*)deque.data_buffer)[deque.head] = data; \
	} \
	else { \
		deque.head = (deque.head - 1 + deque.Capacity) % deque.Capacity; \
		((data_type*)deque.data_buffer)[deque.head] = data; \
	} \
}


/// <summary>
/// 队列尾部添加数据，如果队列满了，弹出头部元素再插入
/// </summary>
/// <param name="deque">队列结构体</param>
/// <param name="data">待添加的数据。如果队列满了，不执行操作</param>
/// <param name="data_type">队列元素类型</param>
#define deque_strong_push_back(deque,data, data_type)  {  \
	if (deque_is_full(deque)) { \
		((data_type*)deque.data_buffer)[deque.tail] = data; \
		deque.head = (deque.head + 1) % deque.Capacity; \
		deque.tail = (deque.tail + 1) % deque.Capacity; \
	} \
	else { \
		((data_type*)deque.data_buffer)[deque.tail] = data; \
		deque.tail = (deque.tail + 1) % deque.Capacity; \
	} \
}



void test_deque(void);


#endif



